Link structure analysis of urban road networks for identifying traffic congestion¶
NetSci 2016 - Diffusion and Transport
Thursday, June 2, 2016 / 16:10-17:50 / Dongkang C, Avenue 3F
Wei Chien Benny Chin, Tzai Hung Wen, and Pei Chun Lai (National Taiwan University, Taiwan)
3 important concepts for identifying congestion distribution¶
- the connectivity: how well is this street (in terms of bringing people to their destination)?
- the demands: how many is the vehicles?
- the design: is its network structure too complex (lots of turning)?
The aim of this study is to understand
the network characteristics that influence the occurance of
traffic congestion.
Link structure analysis of urban road networks for identifying traffic congestion¶
two components:
moving cars and interconnected streets¶
imagine,
the streets are connected to each other, and
there are lots of cars moving on
the streets...
- This is similar to the hyperlinks network of webpages, where people surf from one webpage to another, by the "links".
this study begin with a simple model¶
When a car is moving on a street, it moves along the street.
When it comes to an intersection, it might keep moving straight, or take a turn to the left/right.
At first,
lets just assume that the turning probabilities to the different directions are equal.
turning probability to any next street segment = $ 1/3 $
canvas = toyplot.Canvas(450, 450)
axes = canvas.cartesian()
line = axes.plot(lx,ly, style={"stroke":"steelblue", "stroke-width":10})
line = axes.plot(ly,lx, style={"stroke":"steelblue", "stroke-width":5})
mark = axes.scatterplot(x, y, size=20, marker='s')
canvas.animate(len(x) + 1, callback)
expanded the simple model with the real street network (of Taipei City)
from IPython.display import HTML
HTML('<iframe src="https://player.vimeo.com/video/168713881" width="640"\
height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen \
allowfullscreen></iframe><p><a href="https://vimeo.com/168713881">\
simulation - moving cars on streets taking turn randomly - v0.2</a>\
from <a href="https://vimeo.com/user11082431">Benny Chin</a> on \
<a href="https://vimeo.com">Vimeo</a>.</p>')
this model is similar to the concept behind Google's PageRank (PR) algorithm.
PageRank uses a random move model (the random surfer),
and analyzes the hyperlink connectivity,
namely the referencing network,
to identify the key webpages.
"which pages are referenced more than others."
basic-form: PageRank (Brin & Page, 1998)
$ PR_{t}(i) = \sum_{j\in IN(i)} PR_{t-1}(j) \times \frac{1}{outdeg(j)} $
$ IN(i) $: the incoming node set of i; $ outdeg(j) $: the out-degree of j.
the probability to select each option $ = 1/3 $
Therefore,
we can run the PageRank on the street network,
to identify the important street segment where there are lots of cars would pass by.
The output of PageRank, the score of each street, could be used to represent how important the street is.
the potential demand of the street¶
But,¶
the movements of cars are not completely random in the real world.
main street vs. secondary street
Most of the cars will move along the main direction (keep moving straight).
to capture this concept in the model,
we introduce the "attractiveness" ($attr$) of street segment.
$ attr =$ a composite variable that differentiate the streets by their ability to attract cars.
turning probability:
$ turning = \frac{attr(i)}{\sum_{k\in OUT(j)}attr(k)} $
but, how do we know the distribution of the attractiveness?
- we use Genetic Algorithm (GA) to calibrate the atttractiveness of every street segment by using the VD flow data.
- fitness of GA: the rank correlation between FBPR and the known VD flow.
the modified PR: Flow-based PageRank (FBPR):
$ FBPR_{t}(i) = \sum_{j\in IN(i)} FBPR_{t-1}(j) \times turning $
canvas = toyplot.Canvas(450, 450)
axes = canvas.cartesian()
line = axes.plot(lx,ly, style={"stroke":"steelblue", "stroke-width":10})
line = axes.plot(ly,lx, style={"stroke":"steelblue", "stroke-width":5})
mark = axes.scatterplot(x2, y2, size=20, marker='s')
canvas.animate(len(x2) + 1, callback)
While
the turning probability could be calculated from the calibrated attractiveness,
we could measure
the local complexity of a street.¶
$ entropy(j) = -\sum_{k \in OUT(j)} (turning(j,k) \times ln(turning(j,k))) $
the outgoing entropy¶
the entropy of the turning probabilities origin from the street.
the outgoing entropy -- local complexity
in summary,
- 2 components: moving cars and street network
- turning probabilities are different between the outgoing street
- the FBPR scores could be used to capture the potential demand
- the outgoing entropy represent the local complexity of each street
the three concepts about the congestion¶
- connectivity: run a modified PR algorithm (FBPR) on the street network
- potential demand: the distribution of FBPR scores
- local complexity: the distribution of outgoing entropy
Traffic Congestion¶
the everyday problem for most of the cities in the world.
In most developing countries, the capacity of streets do not meet the rising number of car owners, hence the congestion problem become more serious.
Taipei City
(apart from unexpected factors, e.g. accidents)
Traffic congestion happens while
lots of people go to the same destinations (works, schools) at the same time, putting huge pressure on the street network.
on rush hours
- demand increase
- if the street is complex, the area would easily get into congestion
framework¶
in order to analyze the connectivity of streets, and to measure the demands and design of each street
we propose the Flow-based PageRank.
the study framework
Taipei City
the connectivity¶
the ability of streets for bringing people to their destination.
- analysis unit (nodes): street segment
- connection (links): intersection of street segments
- network: the dual graph of street network
from street network to its dual graph
the (potential) demands¶
the potential number of vehicles passing by the street?
the vehicle detector (VD) data: the real traffic volume data
- a sensor under the street, that count the number of vehicles that is passing above it.
- located at most of the major streets in Taipei City
the street network, and VD location
the design¶
is the network structure too complex?
- moving speed will be slowed down if more vehicles are turning to different direction from a same street.
- the complexity of turning probability between streets is a key measurement to understand traffic congestion </small>
results¶
the simulation¶
HTML('<iframe src="https://player.vimeo.com/video/168714357" width="640"\
height="360" frameborder="0" webkitallowfullscreen mozallowfullscreen \
allowfullscreen></iframe><p><a href="https://vimeo.com/168714357">\
simulation - moving cars on streets turning with the estimated probability\
- v0.2</a> from <a href="https://vimeo.com/user11082431">Benny Chin</a>\
on <a href="https://vimeo.com">Vimeo</a>.</p>')
The distributions of FBPR and outgoing entropy
the FBPR distribution
the outgoing-entropy distribution
The estimated location of congestion
the congested segment: top FBPR overlaped with top entropy
discussions¶
Is the design of the street network meant to be easily get into congestion?¶
if lots of cars started moving at the same times,
will the city become congested easily?
the connectivity¶
- are the streets are connected in an appropriate way?
- are there enough alternative routes that cost similar?
Where are the cars concentrated?¶
- how many cars will pass by a street?
- assuming that cars will now disappear, the cars will always move from one street to a connected street.
- the calculation of the converged FBPR scores will uncover the distribution of the potential needs of movements.
the potential demands¶
Where will the cars turn?¶
- are the cars turn to the same direction?
- outgoing entropy of the turningt probabilities of each street tells us the complexity of the street.
- if the street is less complex, its hierarchy is more significant.eet.
the local complexity¶
Thats all, thanks.¶
my contact info:
Benny Chin,
wcchin.88@gmail.com
a Ph.D. student at National Taiwan University.
links:
- simulation video 1 - random turn: https://vimeo.com/168713881
- simulation video 2 - FBPR turn: https://vimeo.com/168714357